/*
 * @lc app=leetcode.cn id=638 lang=typescript
 *
 * [638] 大礼包
 */

// @lc code=start
function shoppingOffers(price: number[], special: number[][], needs: number[]): number {
  const map: Map<number[], number> = new Map();
  const dfs = (price: number[], special: number[][], currNeeds: number[], n: number): number => {
    if (!map.has(currNeeds)) {
      let minPrice = 0;
      // 按照单价预处理最小价格
      for (let i = 0; i < n; i++) {
        minPrice += currNeeds[i] * price[i];
      }
      // 处理是否可以购买礼包
      for (const sp of special) {
        //
        const nextNeeds = [];
        const specialPrice = sp[n];
        for (let i = 0; i < n; i++) {
          // 礼包内物品数量超过清单的物品数量，无法购买礼包
          if (sp[i] > currNeeds[i]) break;
          // 将剩下的物品数量重新列一个清单
          nextNeeds.push(currNeeds[i] - sp[i]);
          // 礼包内的物品数量都符合清单物品数量
          if (nextNeeds.length === n) {
            // 将新的清单递归
            minPrice = Math.min(minPrice, dfs(price, special, nextNeeds, n) + specialPrice);
          }
        }
      }
      map.set(currNeeds, minPrice);
    }
    return map.get(currNeeds);
  };
  const n = price.length;
  // 有效的礼包
  const filterSpecial = [];
  // 过滤掉无效的礼包
  for (const sp of special) {
    let totalCount = 0;
    let totalPrice = 0;
    for (let i = 0; i < n; i++) {
      totalCount += sp[i];
      totalPrice += sp[i] * price[i];
    }
    // 礼包内有物品且礼包价格要小于正常价格才是优惠礼包
    if (totalCount > 0 && totalPrice > sp[n]) {
      filterSpecial.push(sp);
    }
  }

  return dfs(price, filterSpecial, needs, n);
}
// @lc code=end
